In the paratransit demand-response model, a trip scheduling system has to organize rides between pick-up and drop-off locations that are requested from riders. For example, it is not uncommon that a scheduling system has to divide up to 25,000 daily trip requests among 2,500 or fewer routes (driver shift and vehicle) subject to a multitude of constraints. These constraints include: making pick-ups and drop-offs within each trip's requested 30-minute pickup window and/or appointment window, not exceeding a maximum onboard ride time for each passenger (Maximum Ride Time), not exceeding a vehicle's ambulatory and wheelchair seating capacities, meeting wheelchair LIFO loading and unloading, meeting driver shift start and end times, using different speeds by time period of day, using different speeds in different geographic speed regions or zones, and so on.
Scheduling the routes requires the system be able to calculate an expected travel time between any candidate pair of addresses in the trip request set in order to determine if they can correctly and efficiently be made adjacent stops on a route in a schedule. Travel speeds vary by time period of day (e.g. rush hours or typical congestion, school zones etc.) as well as geographically by law, such as the maximum speed permitted in a geographic region (e.g. speed regions or speed zones), which add more variables to travel time calculations. Empirically, for 25,000 trips, the number of calls to a computer system for travel time estimations between candidate address pairs by time of day can exceed 200,000,000. The travel time prediction calculations are therefore the overwhelming majority of a scheduling system's processing workload.
The speed of the scheduling system is important since the scheduling system is presented with a different trip request set to schedule each day of the year. The time when clients can make trip requests typically ends at 17:00 the evening before. The scheduling system must generally finish scheduling the trip request set by 18:00 or so in order to allow time for the operational staff to make any necessary adjustments and have an IVR (Interactive Voice Response) system call out the pick-up times to all clients by 21:00. Therefore, there is a premium on making the travel time calculations faster.
The accuracy of travel time predictions is also important. Since the actual travel times on the day of service are guaranteed to vary with traffic, weather, and other real-world variables, significant inaccuracies in predicted travel times have a domino effect. A significant error in a predicted travel time that causes a late arrival at a stop propagates the delay forward in time, potentially causing multiple downstream stops to fall outside their committed time windows. This creates messy “pile ups” for dispatchers to untangle on the day of service. This also decreases On-time Performance (OTP), which can have costly financial penalties that may be dictated by negotiated contracts with city or regional governments. Delays can also lead to customer complaints because of late pick-ups, late drop-offs at appointments, and excessive on-board ride times.
Given two addresses and a time period of the day at which a trip is requested, there are various methods for determining the travel time between the addresses. One is to define speed regions as polygons partitioning a service region, each with an associated table of speeds by time period of day. One speed region might correspond to a city center, with a 6 miles per hour average speed in the morning rush hour between 6:30 and 10:30, 5.5 miles per hour average speed in the evening rush hour between 16:00 and 18:30, and 10 miles per hour average in the off rush hour periods. The distance between two addresses (X1,Y1; X2,Y2) can be calculated by triangulation (|X2−X1|+|Y2−Y1|) or by Pythagorean Theorem (SQRT(|X2−X1|2+|Y2−Y1|2)). There are adjustments designed to handle addresses being in different speed regions, crossing rivers on bridges, going around barriers, and so on.
Another approach is to use a GIS representation of a street network, with a speed by time of day associated with each street segment. The distance and travel time between two addresses is calculated by applying a route algorithm such as Dijkstra's algorithm or the A* algorithm, which produces a turn-by-turn route that takes the shortest travel time between the addresses. At each point during the calculation, the travel time to reach that node location (corresponding to a street intersection) from the origin address is known.
U.S. Pat. Nos. 8,036,822 & 8,554,467 describe a static, fixed grid representation overlaying a service area as shown in FIG. 1. The service area is divided into a number of grid sections. Each individual grid section 50 is sized such that the time required to travel from any point to any other point within the individual grid section takes at most an arbitrary constant time, assuming that no obstacles (e.g. rivers, lakes, campuses, parks etc.) are located within the area of the grid section. An obstacle, such as a river, that requires crossing at a bridge in a different grid section that is miles away can introduce a significant inaccuracy in a travel time prediction (with domino effect). This defeats the reliability of this representation for travel time prediction.
As shown in FIG. 2, a river 52 runs through a number of grid sections that reduces the likelihood that a person can travel to any position within the section in the time period that defines the size of the section if the river has to be crossed. One suggested method to minimize the impact of obstacles in a grid section is to divide the section into 4 sub-grid sections 54a-54d as shown in FIG. 2. If the obstacle still appears within a sub-grid section(s), the problem affecting the accuracy of travel time prediction is unsolved, and the sub-grid section(s) with the obstacle are subject to again being sub-divided into 4 smaller grid sections. Even if solved, this approach significantly increases the number of grid sections that need to be considered, which complicates and slows down the travel time predictions.
A similar issue occurs at boundaries between different speed regions as shown in FIG. 3. Here three speed regions 60, 62 and 64 intersect within a grid section such that one grid section 66a encompasses areas with three different maximum rates of travel. If the grid size is calculated such that the travel time between any two points within the grid section takes at most an arbitrary constant time for the faster speed region side of the boundary, the travel time will not be met for points on the slower speed region side(s) of the grid section.
In a similar manner to that used to solve the problem with rivers or other man-made obstacles, one suggested method of minimizing the impact of speed region boundaries is to iteratively divide a grid section into 4 sub-grid sections, until all sub-grid sections meet the requirement for the slowest speed region that appears in that sub-grid section. This significantly increases the number of grid sections that need to be considered, which complicates and slows down travel time prediction calculations.
In a conventional system, the grid boundaries are statically defined once an origin of a Cartesian coordinate system covering the geographic region of interest is defined. A look up table, such as shown in FIG. 4, is defined that stores predicted travel times between grid sections. Because travel times are often not symmetric between addresses, an N×N table is generally used for a geographic area represented by N grid sections.
As will be appreciated, different grids may be defined for different times of day (e.g. smaller grid sections during rush hour) or for different days (weekdays, weekends, holidays etc.) Once the grids sections are defined, the coordinates of the requested pick-up and drop-off locations are mapped onto the grid. Any grid section with a requested pick-up or drop-off location is said to be occupied.
The predicted grid-to-grid section travel times are calculated among occupied grid sections and stored in a travel time look up table (occupied grid section by occupied grid section by time period of day). Any request by the scheduling system for a predicted travel time between a candidate pair of addresses in a trip request set by time period of day can be satisfied by the data in the look up table instead of performing a separate calculation and be limited to at most a 1 minute difference from a calculated result (assuming that each grid section is defined by a travel distance of 30 seconds). Since the actual travel time on the day of service is guaranteed to vary with traffic, weather, and other real-world variables, 1 minute accuracy is more than adequate for planning before the day of service.
Looking up the stored travel times between the grid sections for a particular time of day, is much faster than calculating a predicted travel time between two addresses. Address-to-address calculations are replaced by one grid-to-grid section calculation with a lookup table. If grid section A has 5 addresses, and grid section B has 5 addresses in the morning rush hour, a scheduling system using address-to-address calculations will make 25 requests for travel time predictions. In the grid to grid method, the scheduling system identifies the grid sections for the two addresses, makes 1 request to a travel time prediction routine to populate the travel time table, and thereafter looks up the travel times in the resulting table 24 times. The scheduling system processes much faster with an arbitrarily controlled accuracy of travel times (e.g. within 1 minute).
While the use of a travel time table using grid sections is a significant improvement over calculating the travel times between individual addresses, the system is adversely affected by the problems associated with the issue of obstacles crossing within grid sections and different speed zones in a grid section, which cause inaccurate travel time predictions.